coloring problem

Definition

Given graph $G(V,E)$, the coloring problem asks for an assignment of $k$ colors to vertices $c: V \to \{1,2,...,k\}$. A coloring is proper if adjacent vertices receive different colors, i.e. $\forall (u,v) \in E$, $c(u) \neq c(v)$.

The minimum coloring problem asks for the smallest $k$ to properly color $G$.

The k-coloring problem asks whether $G$ can be properly colored using $k$ colors.

We call the subset of vertices receiving the same color a color class. In a proper coloring every color class is an independent set (i.e. no two vertices in the set are adjacent, meaning no two vertices in the set share an edge).

The chromatic number of a graph is the smallest $k$ such that $G$ admits a k-proper coloring.

3-coloring

Theorem, 3-coloring is NP-complete.

3SAT

References

1. https://www.cs.toronto.edu/~lalla/373s16/notes/3col.pdf